package leetcode.weekly.week331;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	public long minCost(int[] basket1, int[] basket2) {
		TreeMap<Integer, Integer> map = new TreeMap<>();
		TreeMap<Integer, Integer> map1 = new TreeMap<>();
		int min = Integer.MAX_VALUE;
		for (int num : basket1) {
			map.put(num, map.getOrDefault(num, 0) + 1);
			min = Math.min(min, num);
		}
		for (int num : basket2) {
			int size = map.getOrDefault(num, -1);
			if (size != -1) {
				if (size > 1) {
					map.put(num, size - 1);
				} else {
					map.remove(num);
				}
			} else {
				map1.put(num, map1.getOrDefault(num, 0) + 1);
			}
			min = Math.min(min, num);
		}
		int sum = 0, sum1 = 0;
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			if ((entry.getValue() & 1) == 1) {
				return -1;
			}
			sum += entry.getValue();
		}
		for (Map.Entry<Integer, Integer> entry : map1.entrySet()) {
			if ((entry.getValue() & 1) == 1) {
				return -1;
			}
			sum1 += entry.getValue();
		}
		if (sum != sum1) {
			return -1;
		}
		long ans = 0;
		//----
		while (sum > 0) {
			Map.Entry<Integer, Integer> entry = map.firstEntry();
			Map.Entry<Integer, Integer> entry1 = map1.firstEntry();
			int cut = 0, key = 0;
			if (entry.getKey() < entry1.getKey()) {
				cut = Math.min(entry.getValue(), sum);
				key = entry.getKey();
				map.pollFirstEntry();
			} else {
				cut = Math.min(entry1.getValue(), sum);
				key = entry1.getKey();
				map1.pollFirstEntry();
			}
			ans += 1l * Math.min(1l * cut * min, 1l * key * (cut / 2));
			sum -= cut;
		}
		return ans;
	}
//-2009310032
}
